#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        dfs(A, B, C, A.size());
    }

    void dfs(vector<int>& stx, vector<int>& sty, vector<int>& stz, int n)
    {
        if (n == 1) {
            stz.push_back(stx.back());
            stx.pop_back();
            return;
        }
        dfs(stx, stz, sty, n - 1);
        stz.push_back(stx.back());
        stx.pop_back();
        dfs(sty, stx, stz, n - 1);
    }

};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1 && !list2) return nullptr;
        else if (!list1) return list2;
        else if (!list2) return list1;

        if (list1->val <= list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        // cout << 1 << endl;
        // ListNode* ans =  reverseList(head->next);
        ListNode* ans = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        // cout << head->val << endl;
        return ans;
    }

};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* tmp = head->next->next;
        ListNode* pcur = head;
        ListNode* pnext = head->next;
        pnext->next = pcur;
        pcur->next = swapPairs(tmp);
        return pnext;
    }
};

class Solution {
public:
    double myPow(double x, int n) {
        return pow(x, n);
    }
};

class Solution{
public:
    double myPow(double x, int n) {
        if (x == 0) return x;
        double ans = 1;
        double tmp = x;
        if (n < 0) tmp = 1 / tmp;
        n = abs(n);
        while (n > 0) {
            if (n & 1) ans *= tmp;
            tmp *= tmp;
            n >>= 1;
        }
        return ans;
    }
};


class Solution {
public:
    double myPow(double x, int n) {
        return n < 0 ? 1.0 / powpow(x, -(long long)(n)) : powpow(x, n);
    }

    double powpow(double x, long long n)
    {
        if (n == 0) return 1.0;

        double tmp = myPow(x, n / 2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }
};


class Solution {
public:
    double myPow(double x, int n) {
        if (x == 0) return x;
        long long nn = n;
        if (n < 0) {
            nn = abs(n);
            x = 1 / x;
        }
        return powpow(x, nn);
    }

    double powpow(double x, int n)
    {
        if (n == 0) return 1.0;

        double tmp = myPow(x, n / 2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }
};